package com.hyb.algorithm.data.struct.tree;

/**
 *二叉树的最近公共祖先
 * 参考：https://cloud.tencent.com/developer/article/1875014
 * @author huyanbing
 * @create 2023/12/11 5:42 下午
 */
public class LowestCommonAncestor {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return lowestCommonAncestor1(root, p, q);
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor1(root.left, p, q);
        TreeNode right = lowestCommonAncestor1(root.right, p, q);
        if (left != null && right != null) {// 左右子树分别找到了，说明此时的root就是要求的结果
            return root;
        }
        if (left == null) {
            return right;
        }
        return left;
    }
}
